package com.yulongtian.algorithms.binarysearch01;

/**
 * https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/
 * 可
 *
 * @author yulongTian
 * @create 2023-02-10 10:48
 */
public class Test12 {
    public static void main(String[] args) {
        int[] nums1 = {88, 77, 66, 55, 44};
        int[] nums2 = {100, 88, 77, 66, 55};
        System.out.println(maxDistance(nums1, nums2));
    }

    //方法三：参考  双指针
    public static int maxDistance(int[] nums1, int[] nums2) {
        int p1 = 0, p2 = 0;
        int n1 = nums1.length, n2 = nums2.length;
        int max = 0;
        while (p1 < n1 && p2 < n2) {
            if (p2 < p1) p2++;
            else if (nums1[p1] > nums2[p2]) p1++;
            else {
                max = Math.max(max, p2 - p1);
                p2++;
            }
        }
        return max;
    }

//    //方法二：使用二分法  26.52+47.25
//    public static int maxDistance(int[] nums1, int[] nums2) {
//        int ans = 0;
//        for (int i = 0; i < Math.min(nums1.length, nums2.length); i++) {
//            if (nums1[i] > nums2[i]) {
//                continue;
//            }
//            if (nums1[i] <= nums2[nums2.length - 1]) {
//                ans = Math.max(ans, nums2.length - 1 - i);
//                continue;
//            }
//            int left = i;
//            int right = nums2.length - 1;
//            int mid = 0;
//            while (left < right) {
//                mid = left + (right - left + 1) / 2;
//                if (nums1[i] <= nums2[mid]) {
//                    left = mid;
//                } else {
//                    right = mid - 1;
//                }
//                if (left == right) {
//                    mid = left;
//                    break;
//                }
//            }
//            ans = Math.max(ans, mid - i);
//        }
//        return ans;
//    }


//    //方法一：两层for循环  超时  只能通过22/32
//    public static int maxDistance(int[] nums1, int[] nums2) {
//        int ans = 0;
//        for (int p1 = 0; p1 < nums1.length; p1++) {
//            for (int p2 = p1; p2 < nums2.length; p2++) {
//                if (nums1[p1] <= nums2[p2]) {
//                    ans = Math.max(ans, p2 - p1);
//                } else {
//                    break;
//                }
//            }
//        }
//        return ans;
//    }


}
